package com.goldsprite.contourextraction.core;

import java.util.*;

import static com.goldsprite.contourextraction.core.ImageConstants.DIRECTIONS_8;

public class ContourTracer {
	private int[][] grid;
	private boolean[][] visited;
	private int width, height;
	private int searchMode = 1;
	private ArrayList<Contour> contours;

	public List<Contour> traceContours(int[][] inputGrid, boolean onlyVertex) {
		return traceContours(inputGrid, onlyVertex, false);
	}

	public List<Contour> traceContours(int[][] inputGrid, boolean onlyVertex, boolean onlyOutLine) {
		this.grid = binarize(inputGrid);
		this.height = grid.length;
		this.width = grid[0].length;
		this.visited = new boolean[height][width];

		contours = new ArrayList<>();

		// 从左下到右上扫描寻找轮廓起点
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				if (grid[y][x] == 1 && !visited[y][x]) {
					Contour contour = traceSingleContour(x, y, onlyVertex, onlyOutLine);
					if (contour != null) {
						contours.add(contour);
//						return contours;
					}
				}
			}
		}

		return contours;
	}

	private int[][] binarize(int[][] input) {
		int h = input.length;
		int w = input[0].length;
		int[][] result = new int[h][w];

		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				boolean hasValue = input[y][x] > 0;
				boolean isBorder = isBoundaryPoint(input, x, y);
				result[y][x] = hasValue && isBorder ? 1 : 0;
			}
		}
		return result;
	}

	private boolean isOutLineBoundaryPoint(int[][] image, int x, int y, int direction) {
		if (image[y][x] == ImageConstants.BACKGROUND) return false;

		//忽略非上下左右方向
		if(direction % 2 != 0) return true;
		int norDir = (direction + 6) % 8;

		int height = image.length;
		int width = image[0].length;

		// 检查4-邻域是否有背景
		int[] dir = ImageConstants.DIRECTIONS_8[norDir];
		int norX = x + dir[0];
		int norY = y + dir[1];
		if (norX < 0 || norX >= width || norY < 0 || norY >= height) {
			return true; // 图像边界
		}
		if (image[norY][norX] != ImageConstants.BACKGROUND) {
			return false; // 法线方向有图像
		}
		return true;
	}

	private boolean isBoundaryPoint(int[][] image, int x, int y) {
		if (image[y][x] == ImageConstants.BACKGROUND) return false;

		int height = image.length;
		int width = image[0].length;

		// 检查4-邻域是否有背景
		for (int[] dir : ImageConstants.DIRECTIONS_4) {
			int nx = x + dir[0];
			int ny = y + dir[1];

			if (nx < 0 || nx >= width || ny < 0 || ny >= height) {
				return true; // 图像边界
			}
			if (image[ny][nx] == ImageConstants.BACKGROUND) {
				return true; // 空值边界
			}
		}
		return false;
	}

	private Contour traceSingleContour(int startX, int startY) {
		return traceSingleContour(startX, startY, true);
	}

	private Contour traceSingleContour(int startX, int startY, boolean onlyVertex) {
		return traceSingleContour(startX, startY, onlyVertex, false);
	}

	private Contour traceSingleContour(int startX, int startY, boolean onlyVertex, boolean onlyOutLine) {
		Contour contour = new Contour(startX, startY);
		searchMode = 1;
		int chainX = startX;
		int chainY = startY;
		int lastDirection = 0; // 初始方向为右

		//判断是否为外轮廓：依赖初始方向为右
		if(onlyOutLine) {
			for (int i = 0; i < contours.size(); i++) {
				Contour iC = contours.get(i);
				int outX = startX;
				int outY = iC.points.get(0)[1];
				boolean isInnerContour = grid[outY][outX] != ImageConstants.BACKGROUND;
				if (isInnerContour) {
					return null;
				}
			}
		}
//		if (!isOutLineBoundaryPoint(grid, startX, startY, lastDirection)) {
//			return null;
//		}

		// 添加起始点作为第一个顶点
		contour.points.add(new int[]{startX, startY});
//		contour.chainCodes.add(lastDirection);

		do {
			List<Integer> nextDirections = findNextDirection(chainX, chainY, lastDirection);
			if (nextDirections.isEmpty()) {
				return contour;
			}
			int chainCode = nextDirections.get(0);

			chainX = chainX + DIRECTIONS_8[chainCode][0];
			chainY = chainY + DIRECTIONS_8[chainCode][1];
			if (searchMode == 1) {
				contour.chainCodes.add(chainCode);
				contour.points.add(new int[]{chainX, chainY});
				// 移除中间的连线点
				if (onlyVertex && contour.points.size() > 2 && chainCode == lastDirection) {
					contour.chainCodes.remove(contour.chainCodes.size() - 2);
					contour.points.remove(contour.points.size() - 2);
				}
			} else {
				contour.startX = chainX;
				contour.startY = chainY;
				int reverseChainCode = (chainCode + 4) % 8;
				contour.chainCodes.add(0, reverseChainCode);
				contour.points.add(0, new int[]{chainX, chainY});
			}

			// 移动到下一个点
			lastDirection = chainCode;

			// 标记为已访问
			if (chainY >= 0 && chainY < height && chainX >= 0 && chainX < width) {
				visited[chainY][chainX] = true;
			}

		} while (!(chainX == startX && chainY == startY && searchMode == 1));

//        // 确保轮廓闭合
//        if (contour.chainCodes.size() > 0) {
//            contour.vertices.add(new int[]{startX, startY});
//        }

		return contour.chainCodes.size() > 0 ? contour : null;
	}

	private List<Integer> findNextDirection(int x, int y, int lastDirection) {
		// 搜索起点：从上次方向的最右边开始：开始方向为右，转换后为左下
		int startSearch = searchMode == 1 ? (lastDirection + 5) % 8 : (lastDirection + 3) % 8;
		List<Integer> directions = new ArrayList<>();

		// 逆时针搜索8个方向
		for (int i = 0; i < 8; i++) {
			int direction = Math.abs(startSearch + i * (searchMode == 1 ? 1 : -1)) % 8;
			//if(direction % 2 != 0) continue;//改为曼哈顿移动
			int nextX = x + DIRECTIONS_8[direction][0];
			int nextY = y + DIRECTIONS_8[direction][1];

			// 检查边界
			if (nextY >= 0 && nextY < height && nextX >= 0 && nextX < width) {
				visited[nextY][nextX] = true;
				if (grid[nextY][nextX] == 1/* && !visited[nextY][nextX]*/) {
					directions.add(direction);
					if (directions.size() >= 2) break;
				}
			}
		}
		return directions; // 未找到相邻前景点
	}

	public static void convexHullExtraction(List<Contour> contours) {
		for (Contour contour : contours) {
			if (contour.points.size() < 3) {
				continue; // 至少需要3个点才能形成凸包
			}
			// 执行Graham Scan算法
			grahamScan(contour);
		}
	}

	private static void grahamScan(Contour contour) {
		List<int[]> points = new ArrayList<>(contour.points);
		if (points.size() < 3) {
			return;
		}

		// 步骤1: 找到y坐标最小的点（如果y相同则取x最小的）
		//不需要

		// 步骤2: 按极角排序（相对于startPoint）
		//也不需要
		Stack<int[]> stack = new Stack<>();
		stack.push(points.get(0));
		stack.push(points.get(1));

		// 步骤3: 构建凸包
		for (int i = 2; i < points.size(); i++) {
			int[] point1 = stack.get(stack.size() - 2);
			int[] point2 = stack.get(stack.size() - 1);
			int[] point3 = points.get(i);
			int chainCode1 = getVectorAngle(point1, point2);
			int chainCode2 = getVectorAngle(point2, point3);
			boolean onRight = isAngleOnRight(chainCode1, chainCode2);
			boolean onRight2 = false;
			if (stack.size() > 2) {
				point1 = stack.get(stack.size() - 3);
				point2 = stack.get(stack.size() - 2);
				chainCode1 = getVectorAngle(point1, point2);
				chainCode2 = getVectorAngle(point2, point3);
				onRight2 = isAngleOnRight(chainCode1, chainCode2);
			}
			if (onRight || onRight2) {
				stack.pop();
				if (stack.size() < 2)
					stack.push(point3);
				else i--;
			} else {
				stack.push(point3);
			}
		}

		//重新编码(可有可无)
		contour.chainCodes.clear();
		contour.points.clear();
		for (int i = 0; i < stack.size(); i++) {
			contour.points.add(stack.get(i));
			if (i < stack.size() - 1) {
				int chainCode = getChainCode(stack.get(i), stack.get(i + 1));
				contour.chainCodes.add(chainCode);
			}
		}
	}

	public static int getVectorAngle(int[] vec1, int[] vec2) {
		// 计算向量差: vec2 - vec1
		int dx = vec2[0] - vec1[0];
		int dy = vec2[1] - vec1[1];

		// 计算角度（弧度）
		double angleRad = Math.atan2(dy, dx);

		// 转换为角度并确保在 [0, 360) 范围内
		double angleDeg = Math.toDegrees(angleRad);
		if (angleDeg < 0) {
			angleDeg += 360;
		}

		return (int) angleDeg;
	}

	private static int getChainCode(int[] point1, int[] point2) {
		int norX = (int) Math.signum(point2[0] - point1[0]);
		int norY = (int) Math.signum(point2[1] - point1[1]);

		for (int i = 0; i < DIRECTIONS_8.length; i++) {
			int[] dir = ImageConstants.DIRECTIONS_8[i];
			if (dir[0] == norX && dir[1] == norY) {
				return i;
			}
		}
		return -1;
	}

	public static boolean isAngleOnRight(float targetAngle, float referenceAngle) {
		// 计算角度差并归一化到 [-180, 180]
		double diff = normalizeAngle(targetAngle - referenceAngle);
		return diff >= 0;
	}

	private static double normalizeAngle(double angle) {
		angle = angle % 360;
		if (angle > 180) angle -= 360;
		if (angle <= -180) angle += 360;
		return angle;
	}

	private static int getOrientation(int[] p, int[] q, int[] r) {
		long val = (long) (q[1] - p[1]) * (r[0] - p[0]) -
			(long) (q[0] - p[0]) * (r[1] - p[1]);

		if (val == 0) return 0;      // 共线
		return (val > 0) ? 1 : 2;    // 1-顺时针, 2-逆时针
	}

	private static double distance(int[] a, int[] b) {
		return Math.sqrt(Math.pow(b[0] - a[0], 2) + Math.pow(b[1] - a[1], 2));
	}
}
